{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Missing Genetic Value in Each Subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #union-find #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #并查集 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestMissingValueSubtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每棵子树内缺失的最小基因值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一棵根节点为 <code>0</code>&nbsp;的 <strong>家族树</strong>&nbsp;，总共包含 <code>n</code>&nbsp;个节点，节点编号为 <code>0</code>&nbsp;到 <code>n - 1</code>&nbsp;。给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组 <code>parents</code>&nbsp;，其中&nbsp;<code>parents[i]</code>&nbsp;是节点 <code>i</code>&nbsp;的父节点。由于节点 <code>0</code>&nbsp;是 <strong>根</strong>&nbsp;，所以&nbsp;<code>parents[0] == -1</code>&nbsp;。</p>\n",
    "\n",
    "<p>总共有&nbsp;<code>10<sup>5</sup></code>&nbsp;个基因值，每个基因值都用 <strong>闭区间</strong>&nbsp;<code>[1, 10<sup>5</sup>]</code>&nbsp;中的一个整数表示。给你一个下标从&nbsp;<strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，其中&nbsp;<code>nums[i]</code>&nbsp;是节点 <code>i</code>&nbsp;的基因值，且基因值 <strong>互不相同</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个数组<em>&nbsp;</em><code>ans</code>&nbsp;，长度为&nbsp;<code>n</code>&nbsp;，其中&nbsp;<code>ans[i]</code>&nbsp;是以节点&nbsp;<code>i</code>&nbsp;为根的子树内 <b>缺失</b>&nbsp;的&nbsp;<strong>最小</strong>&nbsp;基因值。</p>\n",
    "\n",
    "<p>节点 <code>x</code>&nbsp;为根的 <strong>子树&nbsp;</strong>包含节点 <code>x</code>&nbsp;和它所有的 <strong>后代</strong>&nbsp;节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/23/case-1.png\" style=\"width: 204px; height: 167px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>parents = [-1,0,0,2], nums = [1,2,3,4]\n",
    "<b>输出：</b>[5,1,1,1]\n",
    "<b>解释：</b>每个子树答案计算结果如下：\n",
    "- 0：子树包含节点 [0,1,2,3] ，基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。\n",
    "- 1：子树只包含节点 1 ，基因值为 2 。1 是缺失的最小基因值。\n",
    "- 2：子树包含节点 [2,3] ，基因值分别为 [3,4] 。1 是缺失的最小基因值。\n",
    "- 3：子树只包含节点 3 ，基因值为 4 。1是缺失的最小基因值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/23/case-2.png\" style=\"width: 247px; height: 168px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]\n",
    "<b>输出：</b>[7,1,1,4,2,1]\n",
    "<b>解释：</b>每个子树答案计算结果如下：\n",
    "- 0：子树内包含节点 [0,1,2,3,4,5] ，基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。\n",
    "- 1：子树内包含节点 [1,2] ，基因值分别为 [4,6] 。 1 是缺失的最小基因值。\n",
    "- 2：子树内只包含节点 2 ，基因值为 6 。1 是缺失的最小基因值。\n",
    "- 3：子树内包含节点 [3,4,5] ，基因值分别为 [2,1,3] 。4 是缺失的最小基因值。\n",
    "- 4：子树内只包含节点 4 ，基因值为 1 。2 是缺失的最小基因值。\n",
    "- 5：子树内只包含节点 5 ，基因值为 3 。1 是缺失的最小基因值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]\n",
    "<b>输出：</b>[1,1,1,1,1,1,1]\n",
    "<b>解释：</b>所有子树都缺失基因值 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == parents.length == nums.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>对于&nbsp;<code>i != 0</code>&nbsp;，满足&nbsp;<code>0 &lt;= parents[i] &lt;= n - 1</code></li>\n",
    "\t<li><code>parents[0] == -1</code></li>\n",
    "\t<li><code>parents</code>&nbsp;表示一棵合法的树。</li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code>&nbsp;互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-missing-genetic-value-in-each-subtree](https://leetcode.cn/problems/smallest-missing-genetic-value-in-each-subtree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-missing-genetic-value-in-each-subtree](https://leetcode.cn/problems/smallest-missing-genetic-value-in-each-subtree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,0,2]\\n[1,2,3,4]', '[-1,0,1,0,3,3]\\n[5,4,6,2,1,3]', '[-1,2,3,0,2,4,1]\\n[2,3,4,5,6,7,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from array import array\n",
    "\n",
    "MAXN = 100010\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        self._n = len(nums)\n",
    "        self._parents = parents\n",
    "        self._flag = [False for _ in range(self._n)]\n",
    "\n",
    "        self._ans = [1 for _ in range(self._n)]\n",
    "        self._acc = None\n",
    "        self._link = []\n",
    "\n",
    "        self._indices = array(\"i\", [-1 for _ in range(MAXN)])\n",
    "        for (i, num) in enumerate(nums):\n",
    "            self._indices[num] = i\n",
    "\n",
    "        if self._indices[1] == -1:\n",
    "            return self._ans\n",
    "        \n",
    "        self.__make_link()\n",
    "        \n",
    "        for i in range(2, self._n + 1):\n",
    "            if self._indices[i] == -1:\n",
    "                for x in self._link:\n",
    "                    self._ans[x] = self._acc\n",
    "                return self._ans\n",
    "            \n",
    "            par = self.__get_parent(self._indices[i])\n",
    "            while len(self._link) > 0 and self._link[-1] != par:\n",
    "                last = self._link.pop()\n",
    "                self._flag[last] = False\n",
    "                self._ans[last] = self._acc\n",
    "                self._parents[last] = par\n",
    "            \n",
    "            self._acc += 1\n",
    "        \n",
    "        for x in self._link:\n",
    "            self._ans[x] = self._acc\n",
    "        return self._ans\n",
    "    \n",
    "    def __make_link(self) -> None:\n",
    "        link = []\n",
    "        now = self._indices[1]\n",
    "        while now != -1:\n",
    "            self._flag[now] = True\n",
    "            link.append(now)\n",
    "            now = self._parents[now]\n",
    "        self._link = link[::-1]\n",
    "        self._acc = 2\n",
    "    \n",
    "    def __get_parent(self, x: int) -> int:\n",
    "        if x == -1 or self._flag[x] is True:\n",
    "            return x\n",
    "        self._parents[x] = self.__get_parent(self._parents[x])\n",
    "        return self._parents[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.pa = [i for i in range(n)]\n",
    "        # self.count = n\n",
    "        self.size = [1 for i in range(n)]\n",
    "\n",
    "    def get_size(self, x):\n",
    "        root = self.find(x)\n",
    "        return self.size[root]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])    \n",
    "        return self.pa[x]\n",
    "    \n",
    "    \n",
    "    def merge(self, x, y):  \n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx != rooty:\n",
    "            if self.size[rootx] < self.size[rooty]:\n",
    "                self.pa[rootx] = rooty\n",
    "                self.size[rooty] += self.size[rootx]\n",
    "            else:\n",
    "                self.pa[rooty] = rootx\n",
    "                self.size[rootx] += self.size[rooty]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = parents.__len__()\n",
    "        indegree = [0] * n\n",
    "        q = [-1] * n\n",
    "        for i, v in enumerate(parents):\n",
    "            if v != -1:\n",
    "                indegree[v] += 1\n",
    "        i = 0 \n",
    "        for j, v in enumerate(indegree):\n",
    "            if v == 0:\n",
    "                q[i] = j\n",
    "                i += 1\n",
    "        ans = [1] * len(nums)\n",
    "        dsu = DSU(10**5+5)\n",
    "\n",
    "        k = 0\n",
    "        while k < n:\n",
    "            node = q[k]\n",
    "            while dsu.find(nums[node]) == dsu.find(ans[node]):\n",
    "                ans[node] += 1\n",
    "            if node == 0:\n",
    "                return ans \n",
    "            dsu.merge(nums[node], nums[parents[node]])\n",
    "            ans[parents[node]] = max(ans[parents[node]], ans[node])\n",
    "            indegree[parents[node]] -= 1\n",
    "            if not indegree[parents[node]]:\n",
    "                q[i] = parents[node] \n",
    "                i += 1\n",
    "            k += 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        N = len(parents)\n",
    "        \n",
    "        visited = [0]*N  # 0表示未访问过，1表示值不确定的结点，2表示值确定的已访问结点\n",
    "        \n",
    "        sn = sorted(enumerate(nums), key=lambda x:x[1])  \n",
    "        \n",
    "        low_point, cur_num = sn[0]\n",
    "        if cur_num!=1:  # 如果最小的数字不是1，直接返回\n",
    "            return [1]*N\n",
    "        \n",
    "        p = low_point\n",
    "        \n",
    "        while p!=-1:\n",
    "            visited[p]=1\n",
    "            p = parents[p]\n",
    "        \n",
    "        ans = [1]*N\n",
    "        \n",
    "        for i,n in sn[1:]:\n",
    "            if n!=cur_num+1:  # 当中间有值缺失时，剩下值不确定的结点的值肯定就是那个缺失的值\n",
    "                break\n",
    "                \n",
    "            p = i\n",
    "            while p!=-1:\n",
    "                if visited[p]:\n",
    "                    cur_num += 1\n",
    "                    if visited[p]==1:  \n",
    "                        while low_point!=p:\n",
    "                            ans[low_point]=cur_num\n",
    "                            visited[low_point]=2\n",
    "                            low_point = parents[low_point]\n",
    "                    break\n",
    "                else:\n",
    "                    visited[p]=2\n",
    "                    p = parents[p]\n",
    "        \n",
    "        cur_num+=1\n",
    "        while low_point!=-1:\n",
    "            ans[low_point] = cur_num\n",
    "            low_point = parents[low_point]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(parents)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key = lambda x: nums[x])\n",
    "        ret = [1] * n\n",
    "        if nums[idx[0]] != 1: return ret\n",
    "        c = idx[0]\n",
    "        def fill(start, value, endfa):\n",
    "            nonlocal m\n",
    "            while start != endfa:\n",
    "                ret[start] = value\n",
    "                start = parents[start]\n",
    "                m -= 1\n",
    "            return\n",
    "        vis = set()\n",
    "        def find(i):\n",
    "            while ret[i]:\n",
    "                if i in vis: return\n",
    "                vis.add(i)\n",
    "                i = parents[i]\n",
    "            return i\n",
    "        m = 0\n",
    "        fill(c, 0, -1)\n",
    "        m *= -1\n",
    "        for i in range(1, n):\n",
    "            if nums[idx[i]] != i+1:\n",
    "                fill(c, i+1, -1)\n",
    "            else:\n",
    "                end = find(idx[i])\n",
    "                if not end is None:\n",
    "                    fill(c, i+1, end)\n",
    "                    c = end\n",
    "            if m == 0: return ret\n",
    "        fill(c, n+1, -1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [1] * n\n",
    "        if 1 not in nums:  # 不存在基因值为 1 的点\n",
    "            return ans\n",
    "\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)\n",
    "\n",
    "        vis = [False] * (n + 2)\n",
    "        mex = 2  # 缺失的最小基因值\n",
    "        pre = -1\n",
    "        node = nums.index(1)  # 出发点\n",
    "        while node >= 0:\n",
    "            vis[min(nums[node], n + 1)] = True  # 标记基因值\n",
    "            nodes = [son for son in g[node] if son != pre]\n",
    "            while nodes:\n",
    "                x = nodes.pop()\n",
    "                vis[min(nums[x], n + 1)] = True  # 标记基因值\n",
    "                nodes.extend(g[x])  # 保存接下来需要遍历的点\n",
    "            while vis[mex]:  # node 子树包含这个基因值\n",
    "                mex += 1\n",
    "            ans[node] = mex  # 缺失的最小基因值\n",
    "            pre = node  # 下一轮循环不会遍历 pre 子树\n",
    "            node = parents[node]  # 往上走\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [1] * n\n",
    "        if 1 not in nums:  # 不存在基因值为 1 的点\n",
    "            return ans\n",
    "\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)\n",
    "\n",
    "        vis = [False] * (n + 2)\n",
    "        mex = 2  # 缺失的最小基因值\n",
    "        pre = -1\n",
    "        node = nums.index(1)  # 出发点\n",
    "        while node >= 0:\n",
    "            vis[min(nums[node], n + 1)] = True  # 标记基因值\n",
    "            nodes = [son for son in g[node] if son != pre]\n",
    "            while nodes:\n",
    "                x = nodes.pop()\n",
    "                vis[min(nums[x], n + 1)] = True  # 标记基因值\n",
    "                nodes.extend(g[x])  # 保存接下来需要遍历的点\n",
    "            while vis[mex]:  # node 子树包含这个基因值\n",
    "                mex += 1\n",
    "            ans[node] = mex  # 缺失的最小基因值\n",
    "            pre = node  # 下一轮循环不会遍历 pre 子树\n",
    "            node = parents[node]  # 往上走\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        res = [1] * n\n",
    "        if 1 not in nums:\n",
    "            return res\n",
    "        ch = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            ch[p].append(i)\n",
    "        n1 = nums.index(1)\n",
    "        h = [i for i in range(100005)]\n",
    "        def f(i):\n",
    "            e = i\n",
    "            while h[e] != e:\n",
    "                e = h[e]\n",
    "            while i != e:\n",
    "                h[i], i = e, h[i]\n",
    "            return e\n",
    "        while n1 >= 0:\n",
    "            l = deque([n1])\n",
    "            while l:\n",
    "                c = l.popleft()\n",
    "                h[nums[c]] = h[nums[c] + 1]\n",
    "                for t in ch[c]:\n",
    "                    if res[t] == 1:\n",
    "                        l.append(t)\n",
    "            res[n1] = f(1)\n",
    "            n1 = parents[n1]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        # 不包含1的链，缺失的最小值都是1\n",
    "        ans = [1]*len(nums)\n",
    "        # 如果最小的不是1，那么结果都是1\n",
    "        if 1 not in nums:\n",
    "            return ans\n",
    "        #需要知道儿子节点是什么\n",
    "        g = [[] for _ in nums]\n",
    "        # 注意这里要从1开始，否则parents[0] = -1; g[-1] = [0]，树状图就形成了环\n",
    "        for i in range(1, len(nums)):\n",
    "            g[parents[i]].append(i)\n",
    "        # 用hashmap来存储\n",
    "        vis = set()\n",
    "        # 除了1就是2\n",
    "        min_num = 2\n",
    "        pre = -1\n",
    "        # 从数值为1的点开始进行回溯\n",
    "        node = nums.index(1)\n",
    "        while node != -1:\n",
    "            # 记录接触过的数值\n",
    "            vis.add(nums[node])\n",
    "            # 判断是否有其他分支\n",
    "            tmp = [son for son in g[node] if son!=pre]\n",
    "\n",
    "            while tmp != []:\n",
    "                x = tmp.pop()\n",
    "                # 记录接触过的数值\n",
    "                vis.add(nums[x])\n",
    "                # 这一条子树还没有探索过，所以需要继续探索该分支子树的子树······\n",
    "                tmp.extend(g[x])\n",
    "            \n",
    "            # 不能这么写，因为如果是{1,2,3,4}，那么ans[node]不会改变，而实际应该是5\n",
    "            # for index, num in enumerate(vis):\n",
    "            #     if index+1 != num:\n",
    "            #         ans[node] = index+1\n",
    "\n",
    "            # 最小的数\n",
    "            while min_num in vis:  # node 子树包含这个基因值，遍历vis\n",
    "                min_num += 1\n",
    "            ans[node] = min_num\n",
    "            pre = node\n",
    "            node = parents[node]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans, node, g = [1] * n, -1, [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                node = i\n",
    "            if i:\n",
    "                g[parents[i]].append(i)\n",
    "        if node == -1:\n",
    "            return ans\n",
    "        vis = [False] * 100010\n",
    "        ne, val = node, 2\n",
    "        while node != -1:\n",
    "            self.dfs(node, ne, nums, vis, g)\n",
    "            for i in range(val, n + 2):\n",
    "                if vis[i]:\n",
    "                    continue\n",
    "                ans[node] = val = i\n",
    "                break\n",
    "            ne, node = node, parents[node]\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, node: int, block: int, nums: List[int], vis: List[int], g: List[List[int]]) -> None:\n",
    "        if node > len(g):\n",
    "            return\n",
    "        vis[nums[node]] = True\n",
    "        for son in g[node]:\n",
    "            if son != block:\n",
    "                self.dfs(son, block, nums, vis, g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [1] * n\n",
    "        if 1 not in nums: return ans\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for i, p in enumerate(parents):\n",
    "            g[p].append(i)\n",
    "        u, v, now = nums.index(1), nums.index(1), 1\n",
    "        vis = [False] * 100010\n",
    "        while u != -1:\n",
    "            q = deque([w for w in g[u] if w != v])\n",
    "            vis[nums[u]] = True\n",
    "            while q:\n",
    "                tmp = q.popleft()\n",
    "                vis[nums[tmp]] = True\n",
    "                q.extend(g[tmp])\n",
    "            for i in range(now, 100010):\n",
    "                if vis[i] == False:\n",
    "                    ans[u] = now = i\n",
    "                    break\n",
    "            u, v = parents[u], u\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        res = [1] * len(nums)\n",
    "        if 1 not in nums:\n",
    "            return res\n",
    "        self.visited = set()\n",
    "        graph = [[] for _ in range(len(nums))]\n",
    "        for i in range(1, len(parents)):\n",
    "            graph[parents[i]].append(i)\n",
    "        missing = 2\n",
    "        start = nums.index(1)\n",
    "        while start >= 0:\n",
    "            self.dfs(graph, start, nums)\n",
    "            while missing in self.visited:\n",
    "                missing += 1\n",
    "            res[start] = missing\n",
    "            start = parents[start]    \n",
    "        return res\n",
    "        \n",
    "        \n",
    "    \n",
    "    def dfs(self, graph, start, nums):\n",
    "        if nums[start] in self.visited:\n",
    "            return\n",
    "        self.visited.add(nums[start])\n",
    "        for neighbor in graph[start]:\n",
    "            self.dfs(graph, neighbor, nums)\n",
    "    \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 直接从1开始的节点开始出发向上计算，对于某一个节点来说，如果其子节点没有出现1，那么其值就是1；\n",
    "# 在向遍历父节点的时候，可以用一个变量来记录出现过的最小基因值；\n",
    "# 因为这个过程是从下往上计算的，所以变量val的值是会**越来越大**的。\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        self.adj = self.__Build(parents)\n",
    "        self.value = set()\n",
    "        self.nums = nums\n",
    "\n",
    "        n = len(parents)\n",
    "        self.visited = [0 for _ in range(n)]\n",
    "        res = [1 for _ in range(n)]\n",
    "        # 找到值为1的节点\n",
    "        node = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                node = i\n",
    "                break\n",
    "        if node < 0:\n",
    "            return res\n",
    "\n",
    "        val = 2\n",
    "        while node >= 0:\n",
    "            self.__dfs(node)\n",
    "            while val in self.value:\n",
    "                val += 1\n",
    "            res[node] = val\n",
    "            node = parents[node]\n",
    "        return res\n",
    "\n",
    "    def __Build(self, parents):\n",
    "        n = len(parents)\n",
    "        adj = []\n",
    "        for i in range(n):\n",
    "            adj.append([])\n",
    "        for i in range(1, len(parents)):\n",
    "            adj[parents[i]].append(i)\n",
    "        return adj\n",
    "\n",
    "    def __dfs(self, node):\n",
    "        if self.visited[node] > 0:\n",
    "            return\n",
    "        self.visited[node] = 1\n",
    "        self.value.add(self.nums[node])\n",
    "        for next_node in self.adj[node]:\n",
    "            self.__dfs(next_node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if 1 not in nums:\n",
    "            return [1] * n\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for i, node in enumerate(parents): #parent : children\n",
    "            graph[node].append(i)\n",
    "\n",
    "        vis = set()\n",
    "        res = [1] * n\n",
    "        val = 1\n",
    "        cur_node = nums.index(1) #start from 1\n",
    "\n",
    "        while cur_node != -1:\n",
    "            stack = [cur_node]\n",
    "            vis.add(nums[cur_node])\n",
    "            while stack:\n",
    "                tmp = stack.pop()\n",
    "                vis.add(nums[tmp])\n",
    "                for node in graph[tmp]:\n",
    "                    if nums[node] not in vis:\n",
    "                        vis.add(nums[node])\n",
    "                        stack.append(node)\n",
    "\n",
    "            while val in vis:\n",
    "                val += 1\n",
    "\n",
    "            res[cur_node] = val\n",
    "            cur_node = parents[cur_node]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [1]*n\n",
    "        ma = {}\n",
    "        if 1 not in nums:\n",
    "            return ans\n",
    "        for _ in range(-1,n+1):\n",
    "            ma[_] = []\n",
    "        for i in range(0,n):\n",
    "            j = parents[i]\n",
    "            ma[j].append(i)\n",
    "        node = nums.index(1)\n",
    "        vis = set()\n",
    "        def iau(head):\n",
    "            hi = [head]\n",
    "            vis.add(nums[head])\n",
    "            while len(hi) != 0:\n",
    "                for key in ma[hi[0]]:\n",
    "                    if nums[key] not in vis:\n",
    "                        vis.add(nums[key])\n",
    "                        hi.append(key)\n",
    "                hi.pop(0)\n",
    "        mex = 2\n",
    "        while node >= 0:\n",
    "            iau(node)\n",
    "            while mex in vis:\n",
    "                mex +=1\n",
    "            ans[node] = mex\n",
    "            node = parents[node]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [1] * n\n",
    "        try:\n",
    "            one = nums.index(1)\n",
    "        except ValueError:\n",
    "            return ans\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            rg[parents[i]].append(i)\n",
    "        vis = SortedList()\n",
    "        def dfs(root, ignore):\n",
    "            vis.add(nums[root])\n",
    "            for x in rg[root]:\n",
    "                if x != ignore:\n",
    "                    dfs(x, -1)\n",
    "        lastVis = -1\n",
    "        smallestMiss = 1\n",
    "        while one != -1:\n",
    "            dfs(one, lastVis)\n",
    "            while smallestMiss <= len(vis) and vis[smallestMiss - 1] == smallestMiss:\n",
    "                smallestMiss += 1\n",
    "            ans[one] = smallestMiss\n",
    "            lastVis = one\n",
    "            one = parents[one]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [1] * n\n",
    "        if 1 not in nums:\n",
    "            return ans\n",
    "\n",
    "        # 建树\n",
    "        children = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            children[parents[i]].append(i)\n",
    "\n",
    "        visited = set()    # 记录出现的基因值\n",
    "        def dfs(node):     # 处理基因值\n",
    "            visited.add(nums[node])\n",
    "            for child in children[node]:  # child为node的孩子节点\n",
    "                if nums[child] not in visited:\n",
    "                    dfs(child)\n",
    "        mex = 2\n",
    "        node = nums.index(1)\n",
    "        while node >= 0:\n",
    "            dfs(node)\n",
    "            while mex in visited:\n",
    "                mex += 1\n",
    "            ans[node] = mex\n",
    "            node = parents[node]\n",
    "        return ans      \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [1] * n\n",
    "        #不存在基因值为1的点\n",
    "        if 1 not in nums:\n",
    "            return ans\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)\n",
    "        v = set()\n",
    "        def dfs(x):\n",
    "            v.add(nums[x])\n",
    "            for y in g[x]:\n",
    "                if nums[y] not in v:\n",
    "                    dfs(y)\n",
    "        x = nums.index(1)\n",
    "        mex = 2\n",
    "        while x != -1:\n",
    "            dfs(x)\n",
    "            while mex in v:\n",
    "                mex += 1\n",
    "            ans[x] = mex\n",
    "            x = parents[x]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        child_lst = [[] for i in range(len(nums))]\n",
    "        self.now_idx = -1\n",
    "        for i in range(0, len(nums)):\n",
    "            if i:\n",
    "                child_lst[parents[i]].append(i)\n",
    "            if nums[i] == 1:\n",
    "                self.now_idx = i\n",
    "        \n",
    "        all_child_lst = {}\n",
    "        ans = [1] * len(nums)\n",
    "        visited = [False] * len(nums)\n",
    "    \n",
    "        def dfs(idx: int):\n",
    "            if visited[idx]:\n",
    "                return\n",
    "            all_child_lst[nums[idx]] = True\n",
    "            visited[idx] = True\n",
    "            for c in child_lst[idx]:\n",
    "                dfs(c)\n",
    "        \n",
    "        now_ans = 1\n",
    "        while self.now_idx != -1:\n",
    "            dfs(self.now_idx)\n",
    "            while all_child_lst.get(now_ans) is not None:\n",
    "                now_ans += 1\n",
    "            ans[self.now_idx] = now_ans\n",
    "            self.now_idx = parents[self.now_idx]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        if 1 not in nums:\n",
    "            return [1] * n\n",
    "        g = [[] for v in range(n)]\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1: continue\n",
    "            g[i].append(p)\n",
    "            g[p].append(i)\n",
    "        \n",
    "        vis = set()\n",
    "        def dfs(u):\n",
    "            vis.add(nums[u])\n",
    "            for v in g[u]:\n",
    "                if v == parents[u] or nums[v] in vis: continue\n",
    "                dfs(v)\n",
    "        \n",
    "        ans = [1] * n\n",
    "        u = nums.index(1)\n",
    "        mex = 1\n",
    "        while u != -1:\n",
    "            dfs(u)\n",
    "            while mex in vis:\n",
    "                mex += 1\n",
    "            ans[u] = mex\n",
    "            u = parents[u]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "# -1 0 0 1 3 3\r\n",
    "# 0\r\n",
    "\r\n",
    "# -1,2,3,0,2,4,1\r\n",
    "#  0 1 2 3 4 5 6\r\n",
    "\r\n",
    "# -1 0 1 2 3 2 4\r\n",
    "#  0 3 6 1 2 4 5\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "from collections import defaultdict\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    " \r\n",
    "                            \r\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\r\n",
    "        \r\n",
    "        # 用于访问子树路径\r\n",
    "        def dfs(tree,index):\r\n",
    "            subTree[index] = 1\r\n",
    "            mark[nums[index]] = 1\r\n",
    "            print(index,len(tree[index]))\r\n",
    "            if len(tree[index]) > 0:\r\n",
    "                for idx in tree[index]:\r\n",
    "                    if subTree[idx] == 1:\r\n",
    "                        continue\r\n",
    "                    dfs(tree,idx)\r\n",
    "            else:\r\n",
    "                return \r\n",
    "        \r\n",
    "        tree = defaultdict(list)\r\n",
    "        cur = -1\r\n",
    "        # 记录哪些子树已经被访问过了，防止重复访问\r\n",
    "        subTree = [0]*100010\r\n",
    "        # 记录哪些值已经被使用过了，用于查找最小丢失值\r\n",
    "        mark = [0]*100010\r\n",
    "        # 构造一棵树\r\n",
    "        for i in range(0,len(parents)):\r\n",
    "            if nums[i] == 1:\r\n",
    "                cur = i\r\n",
    "            tree[parents[i]].append(i)\r\n",
    "        # 如果基因值没有为0的，则所有子树最小丢失值为1\r\n",
    "        if cur == -1:\r\n",
    "            ans = [1]*len(parents)\r\n",
    "            return ans\r\n",
    "        else:\r\n",
    "            ans = [1]*len(parents)\r\n",
    "            j = cur\r\n",
    "            last = 1\r\n",
    "            while j != -1:\r\n",
    "                dfs(tree,j)\r\n",
    "                for k in range(last,len(mark)):\r\n",
    "                    if mark[k] == 0:\r\n",
    "                        ans[j] = k\r\n",
    "                        last = k\r\n",
    "                        break\r\n",
    "                j = parents[j]\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        \r\n",
    "            \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        # 建树dfs，递归\n",
    "        # 贪心？不包含1的树结果都是1，所以从1开始自底向上搜就可以了\n",
    "        n = len(parents)\n",
    "        tree = [[] for _ in range(n)]\n",
    "        result = [1] * n\n",
    "        if 1 not in nums:\n",
    "            return result\n",
    "        for i in range(1, n):\n",
    "            tree[parents[i]].append(i)\n",
    "        visit = set()\n",
    "        visit_val = set()\n",
    "        # print(tree)\n",
    "        def dfs(idx):\n",
    "            visit.add(idx)\n",
    "            visit_val.add(nums[idx])\n",
    "            for node in tree[idx]:\n",
    "                if node not in visit:\n",
    "                    dfs(node)\n",
    "        cache = 2\n",
    "        node = nums.index(1)\n",
    "        while node >= 0:\n",
    "            dfs(node)\n",
    "            while cache in visit_val:\n",
    "                cache += 1\n",
    "            result[node] = cache\n",
    "            node = parents[node]\n",
    "        return result\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def smallestMissingValueSubtree(self, parents, nums):\n",
    "        \"\"\"\n",
    "        :type parents: List[int]\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(parents)\n",
    "        g = {x: set() for x in range(n)}\n",
    "        for index, fa in enumerate(parents):\n",
    "            if fa != -1:\n",
    "                g[fa].add(index)\n",
    "\n",
    "        res = [1] * n\n",
    "        p = None\n",
    "        for index, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                p = index\n",
    "                break\n",
    "\n",
    "        if p is None:\n",
    "            return res\n",
    "\n",
    "        num_set = set()\n",
    "        num_set.add(1)\n",
    "        q = [p]\n",
    "        l = 0\n",
    "        r = 1\n",
    "        while l < r:\n",
    "            now = q[l]\n",
    "            l += 1\n",
    "            for next in g[now]:\n",
    "                num_set.add(nums[next])\n",
    "                q.append(next)\n",
    "                r += 1\n",
    "\n",
    "        miss = 2\n",
    "        while miss in num_set:\n",
    "            miss += 1\n",
    "        res[p] = miss\n",
    "\n",
    "        while parents[p] != -1:\n",
    "            q = [parents[p]]\n",
    "            num_set.add(nums[parents[p]])\n",
    "            l = 0\n",
    "            r = 1\n",
    "            while l < r:\n",
    "                now = q[l]\n",
    "                l += 1\n",
    "                for next in g[now]:\n",
    "                    if next == p:\n",
    "                        continue\n",
    "                    num_set.add(nums[next])\n",
    "                    q.append(next)\n",
    "                    r += 1\n",
    "\n",
    "            while miss in num_set:\n",
    "                miss += 1\n",
    "\n",
    "            res[parents[p]] = miss\n",
    "            p = parents[p]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        # 建树\n",
    "        from collections import defaultdict\n",
    "        reverse = defaultdict(list)\n",
    "        for node,parent in enumerate(parents):\n",
    "            reverse[parent].append(node) # 叶子节点不在reverse中\n",
    "\n",
    "        def dfs(node: int) -> None:\n",
    "            \"\"\"遍历以node为根的树\"\"\"\n",
    "            visit.add(nums[node])\n",
    "            if node in reverse:\n",
    "                for child_node in reverse[node]:\n",
    "                    if nums[child_node] not in visit:\n",
    "                        dfs(child_node)\n",
    "\n",
    "\n",
    "        length = len(parents)\n",
    "        visit = set()\n",
    "        ans = [1]*length\n",
    "        if 1 not in nums:\n",
    "            return ans\n",
    "        node = nums.index(1) # 出发点\n",
    "        mex = 2\n",
    "        while node >= 0:\n",
    "            dfs(node)\n",
    "            while mex in visit: # 以node为根的树中包含了mex值的节点\n",
    "                mex += 1\n",
    "            ans[node] = mex\n",
    "            node = parents[node]\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        children = defaultdict(list)\n",
    "        # 先构造树\n",
    "        for i, x in enumerate(parents):\n",
    "            children[x].append(i)\n",
    "\n",
    "        # 记录每个节点的访问状态\n",
    "        visited = [False] * n\n",
    "        geneSet = set()\n",
    "        # 深度遍历树\n",
    "\n",
    "        def dfs(node: int) -> None:\n",
    "            if visited[node]:\n",
    "                return\n",
    "            visited[node] = True\n",
    "            geneSet.add(nums[node])\n",
    "            if node in children:\n",
    "                for c in children[node]:\n",
    "                    dfs(c)\n",
    "\n",
    "        node = nums.index(1) if 1 in nums else -1\n",
    "        res, testMissing = [1] * n, 1  # test\n",
    "\n",
    "        while node != -1:\n",
    "            dfs(node)\n",
    "            while testMissing in geneSet:\n",
    "                testMissing += 1\n",
    "            res[node], node = testMissing, parents[node]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "\n",
    "    def union(self, idx1, idx2):\n",
    "        self.p[self.find(idx2)] = self.find(idx1)\n",
    "    \n",
    "    def find(self, idx):\n",
    "        if self.p[idx] != idx:\n",
    "            self.p[idx] = self.find(self.p[idx])\n",
    "        return self.p[idx]\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        res = [1]*n\n",
    "        now = -1\n",
    "        for i, e in enumerate(parents):\n",
    "            if i != 0:\n",
    "                g[e].append(i)\n",
    "            if nums[i] == 1:\n",
    "                now = i\n",
    "        union = UnionFind(n+2)\n",
    "        last = -1\n",
    "        nowres = 2\n",
    "        while now != -1:\n",
    "            stack = [now]\n",
    "            while stack:\n",
    "                root = stack.pop()\n",
    "                for nex in g[root]:\n",
    "                    if nex != last:\n",
    "                        union.union(nums[root], nums[nex])\n",
    "                        stack.append(nex)\n",
    "            while union.find(nowres) == union.find(nums[now]):\n",
    "                nowres += 1\n",
    "            res[now] = nowres\n",
    "            last = now\n",
    "            now = parents[now]\n",
    "            union.union(nums[now], nums[last])\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        children = defaultdict(list)\n",
    "        for i,j in enumerate(parents):\n",
    "            children[j].append(i)\n",
    "        \n",
    "        n = len(nums)\n",
    "        seen = [0] * (n+2)\n",
    "        ans = [1] * n\n",
    "        p = 1\n",
    "\n",
    "        def visit(i):\n",
    "            v = nums[i]\n",
    "            if not seen[v]:\n",
    "                seen[v] = 1\n",
    "                for j in children[i]:\n",
    "                    visit(j)\n",
    "\n",
    "        try:\n",
    "            i = nums.index(1)\n",
    "        except:\n",
    "            i = -1\n",
    "\n",
    "        while i != -1:\n",
    "            visit(i)\n",
    "            while seen[p] == 1:\n",
    "                p += 1\n",
    "            ans[i] = p\n",
    "            i = parents[i]\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        if 1 not in nums: return [1] * len(parents)\n",
    "        d_path = defaultdict(list)\n",
    "        for idx, val in enumerate(parents):\n",
    "            if val >= 0: d_path[val].append(idx)\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num == 1: break\n",
    "\n",
    "        note = [0] * len(parents)\n",
    "        visited = [0] * len(parents)\n",
    "        def dfs(pt):\n",
    "            if visited[pt] == 0:\n",
    "                visited[pt] = 1\n",
    "                if nums[pt] - 1 < len(nums): note[nums[pt] - 1] = 1\n",
    "                for new_pt in d_path[pt]:\n",
    "                    dfs(new_pt)\n",
    "\n",
    "        res = [1] * len(parents)\n",
    "        tmp_pos = 0\n",
    "        while idx != -1:\n",
    "            dfs(idx)\n",
    "            while tmp_pos < len(nums) and note[tmp_pos] == 1:\n",
    "                tmp_pos += 1\n",
    "            res[idx] = tmp_pos + 1\n",
    "            idx = parents[idx]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        res = [1] * len(nums)\n",
    "        if 1 not in nums:\n",
    "            return res \n",
    "\n",
    "        tree = defaultdict(list)\n",
    "        for node,parent in enumerate(parents):\n",
    "            tree[parent].append(node)\n",
    "\n",
    "        def dfs(node, vis):\n",
    "            if nums[node] in vis:\n",
    "                return \n",
    "            vis.add(nums[node])\n",
    "            for nxt in tree[node]:\n",
    "                dfs(nxt,vis)\n",
    "\n",
    "        node = nums.index(1)\n",
    "        mex = 2\n",
    "        vis = set()\n",
    "        while node != -1:\n",
    "            dfs(node, vis)\n",
    "            while mex in vis:\n",
    "                mex += 1\n",
    "            res[node] = mex \n",
    "            node = parents[node]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        def dfs(u):\n",
    "            nonlocal seen\n",
    "            seen.add(nums[u])\n",
    "            for v in g[u]:\n",
    "                dfs(v)\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = [1] * n\n",
    "        u = 0\n",
    "        try:\n",
    "            u = nums.index(1)\n",
    "        except ValueError:\n",
    "            return ans\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for i, p in enumerate(parents):\n",
    "            g[p].append(i)\n",
    "\n",
    "        smv = 1\n",
    "        seen = set()\n",
    "        while u >= 0:            \n",
    "            for v in g[u]:\n",
    "                if nums[v] not in seen:\n",
    "                    dfs(u)\n",
    "            seen.add(nums[u])\n",
    "            # print(u, seen)\n",
    "            while smv in seen:\n",
    "                smv += 1\n",
    "            ans[u] = smv\n",
    "            u = parents[u]\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ret = [1] * n\n",
    "        if 1 not in nums:\n",
    "            return ret\n",
    "\n",
    "        g = collections.defaultdict(list)\n",
    "        for i, p in enumerate(parents[1:], start=1):\n",
    "            g[p].append(i)\n",
    "\n",
    "        vis = set()\n",
    "\n",
    "        def dfs(x):\n",
    "            vis.add(nums[x])\n",
    "            for son in g[x]:\n",
    "                if nums[son] not in vis:\n",
    "                    dfs(son)\n",
    "\n",
    "        gene = 2\n",
    "        node = nums.index(1)\n",
    "        while node >= 0:\n",
    "            dfs(node)\n",
    "            while gene in vis:\n",
    "                gene += 1\n",
    "\n",
    "            ret[node] = gene\n",
    "            node = parents[node]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(parents)\n",
    "        nxt = [set() for i in range(n)]\n",
    "        for idx, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            nxt[p].add(idx)\n",
    "\n",
    "        vis = set()\n",
    "\n",
    "        def dfs(idx):\n",
    "            if nums[idx] in vis:\n",
    "                return\n",
    "            vis.add(nums[idx])\n",
    "            for node in nxt[idx]:\n",
    "                dfs(node)\n",
    "            return\n",
    "        \n",
    "        ans = [1] * n\n",
    "        # every ans for parent node will [>=] each ans of its sons\n",
    "        p = 1\n",
    "        if 1 not in nums:\n",
    "            return ans\n",
    "        cur = nums.index(1)\n",
    "        while cur != -1:\n",
    "            dfs(cur)\n",
    "            while p in vis:\n",
    "                p += 1\n",
    "            ans[cur] = p\n",
    "            cur = parents[cur]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\r\n",
    "        n = len(parents)\r\n",
    "        res = [1] * n\r\n",
    "        if 1 not in set(nums):\r\n",
    "            return res\r\n",
    "\r\n",
    "        # # find children 这种方法比下面的方法慢很多\r\n",
    "        # children = collections.defaultdict(list)\r\n",
    "        # for idx,i in enumerate(parents):\r\n",
    "        #     children[i].append(idx)\r\n",
    "\r\n",
    "        \r\n",
    "        # children = [[] for _ in range(n)]\r\n",
    "        children = collections.defaultdict(list)\r\n",
    "        for i in range(1, n):\r\n",
    "            children[parents[i]].append(i)\r\n",
    " \r\n",
    "        geneSet = set()\r\n",
    "        visited = [False] * n\r\n",
    "        def dfs(node):\r\n",
    "            if visited[node]:\r\n",
    "                return\r\n",
    "            visited[node] = True\r\n",
    "            geneSet.add(nums[node])\r\n",
    "            for child in children[node]:\r\n",
    "                dfs(child)\r\n",
    "\r\n",
    "        node = nums.index(1) if 1 in nums else -1\r\n",
    "        iNode = 1\r\n",
    "\r\n",
    "        while node != -1:\r\n",
    "            dfs(node)\r\n",
    "            while iNode in geneSet:\r\n",
    "                iNode += 1\r\n",
    "            res[node], node = iNode, parents[node]\r\n",
    "        return res\r\n",
    "\r\n",
    "\r\n",
    "        return res\r\n",
    "\r\n",
    "        \r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        children = defaultdict(list)\n",
    "        for i,x in enumerate(parents):\n",
    "            if x>=0:\n",
    "                children[x].append(i) \n",
    "        # 计算每个节点的深度\n",
    "        depth = {0:0}\n",
    "        bfs = [0]\n",
    "        while bfs:\n",
    "            x = bfs.pop(0)\n",
    "            for y in children[x]:\n",
    "                depth[y] = depth[x] + 1\n",
    "                bfs.append(y)\n",
    "        # 从最底层开始简并\n",
    "        level = defaultdict(list)\n",
    "        maxLevel = 0\n",
    "        for x in depth:\n",
    "            y = depth[x]\n",
    "            level[y].append(x)\n",
    "            maxLevel = max(maxLevel, y)\n",
    "        rv = [0]*len(parents)\n",
    "        gene = {} \n",
    "        for y in level[maxLevel]:\n",
    "            gene[y] = MySortedList(nums[y])\n",
    "            rv[y] = gene[y].value  \n",
    "        for t in reversed(range(maxLevel)):\n",
    "            for y in level[t]:\n",
    "                gene[y] = MySortedList(nums[y]) \n",
    "                for x in children[y]:\n",
    "                    gene[y].join(gene[x])\n",
    "                rv[y] = gene[y].value  \n",
    "        return rv \n",
    " \n",
    "class MySortedList:\n",
    "    def __init__(self,v): \n",
    "        self.arr = [v]\n",
    "\n",
    "    def join(self, other):\n",
    "        n = len(self.arr)\n",
    "        m = len(other.arr)\n",
    "        if n==1:\n",
    "            t = self.arr[0]\n",
    "            rv = other.arr \n",
    "            i = bisect_left(rv,t)\n",
    "            if i<len(rv) and rv[i]==t:\n",
    "                self.arr = rv \n",
    "            else:\n",
    "                rv.insert(i,t)\n",
    "                self.arr = rv \n",
    "            return \n",
    "        if m==1:\n",
    "            t = other.arr[0]\n",
    "            rv = self.arr \n",
    "            i = bisect_left(rv,t)\n",
    "            if i<len(rv) and rv[i]==t:\n",
    "                self.arr = rv \n",
    "            else:\n",
    "                rv.insert(i,t)\n",
    "                self.arr = rv \n",
    "            return \n",
    "        rv = [] \n",
    "        i = j = 0 \n",
    "        while i<n and j<m:\n",
    "            x = self.arr[i]\n",
    "            y = other.arr[j]\n",
    "            if x==y:\n",
    "                rv.append(x)\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif x<y:\n",
    "                rv.append(x)\n",
    "                i += 1\n",
    "            else:\n",
    "                rv.append(y)\n",
    "                j += 1\n",
    "        while i<n:\n",
    "            x = self.arr[i]\n",
    "            rv.append(x)\n",
    "            i += 1\n",
    "        while j<m:\n",
    "            y = other.arr[j]\n",
    "            rv.append(y)\n",
    "            j += 1 \n",
    "        self.arr = rv \n",
    "\n",
    "    @property\n",
    "    def value(self):\n",
    "        n = len(self.arr)\n",
    "        if n==0:\n",
    "            return 1\n",
    "        if self.arr[0]>1:\n",
    "            return 1\n",
    "        if self.arr[n-1] == n:\n",
    "            return n+1\n",
    "        left = 0\n",
    "        right = n-1 \n",
    "        nums = self.arr \n",
    "        while right-left>3:\n",
    "            mid = (left+right)//2 \n",
    "            x = nums[mid]\n",
    "            if x==mid+1:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid \n",
    "        for x in range(left, right+1):\n",
    "            if nums[x]!=x+1:\n",
    "                return x+1\n",
    "        return -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        children_dict = defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            children_dict[parents[i]].append(i)\n",
    "        \n",
    "        value_set = set()\n",
    "        visited_set = set()\n",
    "\n",
    "        def visit(node):\n",
    "            if node in visited_set:\n",
    "                return\n",
    "            \n",
    "            visited_set.add(node)\n",
    "            value_set.add(nums[node])\n",
    "            for child in children_dict[node]:\n",
    "                visit(child)\n",
    "        \n",
    "        res = [1] * n\n",
    "\n",
    "        current_node = nums.index(1) if 1 in nums else -1\n",
    "        current_value = 1\n",
    "\n",
    "        while current_node != -1:\n",
    "            visit(current_node)\n",
    "            while current_value in value_set:\n",
    "                current_value += 1\n",
    "            \n",
    "            res[current_node] = current_value\n",
    "            current_node = parents[current_node]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        def dfs(i):\n",
    "            if i in visited:\n",
    "                return\n",
    "            visited.add(i)\n",
    "            geneSet.add(nums[i])\n",
    "            for child in p_sons[i]:\n",
    "                dfs(child)\n",
    "            pass\n",
    "\n",
    "        n = len(parents)\n",
    "        p_sons = defaultdict(list)\n",
    "        for s, p in enumerate(parents):\n",
    "            p_sons[p].append(s)\n",
    " \n",
    "        geneSet = set()\n",
    "        visited = set()\n",
    "\n",
    "        node = nums.index(1) if 1 in nums else -1\n",
    "        ans, iNode = [1] * n, 1\n",
    "\n",
    "        while node != -1:\n",
    "            dfs(node)\n",
    "            while iNode in geneSet:\n",
    "                iNode += 1\n",
    "            ans[node], node = iNode, parents[node]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        childs = defaultdict(list)\n",
    "        for i,p in enumerate(parents):\n",
    "            childs[p].append(i)\n",
    "        childs.pop(-1)\n",
    "        N = len(parents)\n",
    "        data = {}\n",
    "        def add(p,n):\n",
    "            st, m = data[p]\n",
    "            st.add(n)\n",
    "            while(m in st):\n",
    "                m+=1\n",
    "            data[p][1]=m\n",
    "            return m\n",
    "        \n",
    "        def update(p,c):\n",
    "            parent = data[p]\n",
    "            child = data[c]\n",
    "            parent[0]|=child[0]\n",
    "            st,m = parent\n",
    "            while(m in st):\n",
    "                m+=1\n",
    "            parent[1] = m\n",
    "            return m\n",
    "                \n",
    "            \n",
    "        res = [1]*N\n",
    "            \n",
    "        BFS = [0]\n",
    "        for p in BFS:\n",
    "            if p in childs:\n",
    "                BFS.extend(childs[p])\n",
    "            else:\n",
    "                data[p] = [set(),1]\n",
    "        # print(BFS)\n",
    "        \n",
    "        BFS.reverse()\n",
    "        for p in BFS:\n",
    "            assert p in data, 'assigned?'\n",
    "            res[p] = add(p,nums[p])\n",
    "            par = parents[p]\n",
    "            if par in data:\n",
    "                update(par,p)\n",
    "            else:\n",
    "                data[par] = data[p]\n",
    "        \n",
    "        return( res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        def dfs(p,contains)->set:\n",
    "            result = {nums[p]}\n",
    "            for child in graph[p]:\n",
    "                if nums[child] in contains:\n",
    "                    continue\n",
    "                result |= dfs(child,contains)\n",
    "            return result\n",
    "\n",
    "        graph = defaultdict(set)\n",
    "        for child in range(len(parents)):\n",
    "            graph[parents[child]].add(child)\n",
    "\n",
    "        index = [i for i in range(len(nums)) if nums[i] == 1]\n",
    "        result = [1]*len(parents)\n",
    "        if not index:\n",
    "            return result\n",
    "        p = index[0]\n",
    "        i = 1\n",
    "        contains = set()\n",
    "        while p != -1:\n",
    "            contains |= dfs(p,contains)\n",
    "            while i in contains:\n",
    "                contains.discard(i)\n",
    "                i += 1\n",
    "            result[p] = i\n",
    "            p = parents[p]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        def dfs(p):\n",
    "            nonlocal contains\n",
    "            contains.add(nums[p])\n",
    "            for child in graph[p]:\n",
    "                if nums[child] in contains:\n",
    "                    continue\n",
    "                dfs(child)\n",
    "\n",
    "        graph = defaultdict(set)\n",
    "        for child in range(len(parents)):\n",
    "            graph[parents[child]].add(child)\n",
    "\n",
    "        result = [1]*len(parents)\n",
    "        if nums.count(1) == 0:\n",
    "            return result\n",
    "        p = nums.index(1)\n",
    "        i = 1\n",
    "        contains = set()\n",
    "        while p != -1:\n",
    "            dfs(p)\n",
    "            while i in contains:\n",
    "                i += 1\n",
    "            result[p] = i\n",
    "            p = parents[p]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        degree = [0] * n\n",
    "        for p in parents:\n",
    "            if p >= 0:\n",
    "                degree[p] += 1\n",
    "        a = []\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                a.append(i)\n",
    "        res = [1] * n\n",
    "        i = 0\n",
    "        dnas = [(1, {nums[i]}) for i in range(n)]\n",
    "        while i < len(a):\n",
    "            x = a[i]\n",
    "            i += 1\n",
    "            k, s = dnas[x]\n",
    "            while k in s:\n",
    "                s.remove(k)\n",
    "                k += 1\n",
    "            res[x] = k\n",
    "            y = parents[x]\n",
    "            if y >= 0:\n",
    "                kk, ss = dnas[y]\n",
    "                kk = max(k, kk)\n",
    "                if len(s) > len(ss):\n",
    "                    s, ss = ss, s\n",
    "                for x in s:\n",
    "                    if x >= kk:\n",
    "                        ss.add(x)\n",
    "                dnas[y] = (kk, ss)\n",
    "                degree[y] -= 1\n",
    "                if degree[y] == 0:\n",
    "                    a.append(y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        \n",
    "        fa = list(range(10**5+2))\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x,y):\n",
    "            fx = find(x);fy = find(y)\n",
    "            fa[fx] = fy\n",
    "        \n",
    "        n = len(parents)\n",
    "        g = [[]for _ in range(n)]\n",
    "        for i,p in enumerate(parents):\n",
    "            if p!=-1:\n",
    "                g[p].append(i)\n",
    "\n",
    "        def dfs(x):\n",
    "            merge(nums[x],nums[x]+1)  \n",
    "            for y in g[x]:\n",
    "                if not vis[y]:\n",
    "                    vis[y] = True\n",
    "                    dfs(y)\n",
    "        \n",
    "        \n",
    "        vis = [False]*n \n",
    "        ans = [1]*n \n",
    "        hasone = -1\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                hasone = i;break\n",
    "        if hasone<0:\n",
    "            return ans\n",
    "        \n",
    "        path = [hasone]\n",
    "        pa = hasone\n",
    "        while pa!=0:\n",
    "            pa = parents[pa]\n",
    "            path.append(pa)\n",
    "         \n",
    "        for pa in path:\n",
    "            vis[pa]=True\n",
    "            dfs(pa) \n",
    "            ans[pa] = find(1)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        _, s, _ = nums.append(1), nums.index(1), nums.pop()\n",
    "        ans = [1] * n\n",
    "        if s == n:  # nums里没有1，直接返回全1\n",
    "            return ans\n",
    "        children = collections.defaultdict(set)\n",
    "        for c, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            children[p].add(c)\n",
    "        path = [s]\n",
    "        while s != 0:\n",
    "            s = parents[s]\n",
    "            path.append(s)\n",
    "        \n",
    "        genes = [0] * (10 ** 5 + 2)\n",
    "        def dfs(node, start=None):\n",
    "            nonlocal genes\n",
    "            genes[nums[node]] = 1\n",
    "            for c in children[node]:\n",
    "                if genes[nums[c]] == 0:  # 防止自底向上过程中有节点重入\n",
    "                    dfs(c, None)\n",
    "            if start is not None:  # 从孩子节点的结果出发，继续搜索\n",
    "                for i in range(start, n + 2):\n",
    "                    if not genes[i]:\n",
    "                        return i\n",
    "\n",
    "        last = 1\n",
    "        for node in path:\n",
    "            ans[node] = dfs(node, last)\n",
    "            last = ans[node]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        _, s, _ = nums.append(1), nums.index(1), nums.pop()\n",
    "        ans = [1] * n\n",
    "        if s == n:\n",
    "            return ans\n",
    "        children = collections.defaultdict(set)\n",
    "        for c, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            children[p].add(c)\n",
    "        path = [s]\n",
    "        while s != 0:\n",
    "            s = parents[s]\n",
    "            path.append(s)\n",
    "        \n",
    "        genes = [0] * (10 ** 5 + 2)\n",
    "        @cache\n",
    "        def dfs(node, start=None):\n",
    "            nonlocal genes\n",
    "            genes[nums[node]] = 1\n",
    "            for c in children[node]:\n",
    "                dfs(c, None)\n",
    "            if start is not None:\n",
    "                for i in range(start, n + 2):\n",
    "                    if not genes[i]:\n",
    "                        return i\n",
    "        last = 1\n",
    "        for node in path:\n",
    "            ans[node] = dfs(node, last)\n",
    "            last = ans[node]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        son_dict = collections.defaultdict(set)\n",
    "        for i, p in enumerate(parents[1:]):\n",
    "            son_dict[p].add(i+1)\n",
    "        n = len(parents)\n",
    "        ans_list = [1] * n\n",
    "        if 1 not in nums:\n",
    "            return ans_list\n",
    "        visited = set()\n",
    "        def dfs(x):\n",
    "            visited.add(nums[x])\n",
    "            for son in son_dict[x]:\n",
    "                if nums[son] not in visited:\n",
    "                    dfs(son)\n",
    "\n",
    "        m = 2\n",
    "        node = nums.index(1)\n",
    "        while node >= 0:\n",
    "            dfs(node)\n",
    "            while m in visited:\n",
    "                m += 1\n",
    "            ans_list[node] = m\n",
    "            node = parents[node]\n",
    "        return ans_list\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        children = collections.defaultdict(set)\n",
    "        for i in range(len(parents)):\n",
    "            children[parents[i]].add(i)\n",
    "        ans = [0]*len(parents)\n",
    "        val = {}\n",
    "        for i in range(len(nums)):\n",
    "            val[nums[i]] = i\n",
    "        s = set()\n",
    "        f = 2\n",
    "\n",
    "        def dfs1(m):\n",
    "            for i in children[m]:\n",
    "                s.add(nums[i])\n",
    "                ans[i] = 1\n",
    "                dfs1(i)\n",
    "\n",
    "        def dfs2(m,q):\n",
    "            for i in children[m]:\n",
    "                if i != q:\n",
    "                    s.add(nums[i])\n",
    "                    ans[i] = 1\n",
    "                    dfs2(i,q)\n",
    "\n",
    "        if 1 not in val:\n",
    "            return [1]*len(parents)\n",
    "        else:\n",
    "            q = val[1]\n",
    "            dfs1(q)\n",
    "            s.add(nums[q])\n",
    "            while f in s:\n",
    "                f += 1\n",
    "            ans[q] = f\n",
    "            p = parents[q]\n",
    "            while p != -1:\n",
    "                dfs2(p,q)\n",
    "                s.add(nums[p])\n",
    "                while f in s:\n",
    "                    f += 1\n",
    "                ans[p] = f\n",
    "                q = p\n",
    "                p = parents[q]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        sons = defaultdict(set)\n",
    "        for i, parent in enumerate(parents):\n",
    "            sons[parent].add(i)\n",
    "\n",
    "        def dfs(i):\n",
    "            visited.add(nums[i])\n",
    "            for i_son in sons[i]:\n",
    "                if nums[i_son] not in visited:\n",
    "                    dfs(i_son)\n",
    "\n",
    "        ans = [1 for _ in range(n)]\n",
    "        visited = set()\n",
    "        if 1 not in nums:\n",
    "            return ans\n",
    "        now_node = nums.index(1)\n",
    "        visited.add(1)\n",
    "\n",
    "        cur_value = 2\n",
    "        while now_node != -1:\n",
    "            dfs(now_node)\n",
    "            while cur_value in visited:\n",
    "                cur_value += 1\n",
    "            ans[now_node] = cur_value\n",
    "            now_node = parents[now_node]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        #每个节点的子节点\n",
    "        d_son = defaultdict(set)\n",
    "\n",
    "        for i, p in enumerate(parents):\n",
    "            d_son[p].add(i)\n",
    "\n",
    "        class Node:\n",
    "            def __init__(self, i, p=None):\n",
    "                self.i = i\n",
    "                self.p = p\n",
    "\n",
    "                if nums[i] == 1:\n",
    "                    self.nums = {1, 100002}\n",
    "                    self.ret = 2\n",
    "                else:\n",
    "                    self.nums = {nums[i]}\n",
    "                    self.ret = 1\n",
    "\n",
    "            def add(self, n):\n",
    "                if len(self.nums) >= len(n.nums):\n",
    "                    self.nums.update(n.nums)\n",
    "                else:\n",
    "                    n.nums.update(self.nums)\n",
    "                    self.nums = n.nums\n",
    "\n",
    "                if n.ret > self.ret:\n",
    "                    self.ret = n.ret\n",
    "                while self.ret in self.nums:\n",
    "                    self.ret += 1\n",
    "\n",
    "        #将树转为根节点开始的list\n",
    "        l_node = [[Node(0)]]\n",
    "\n",
    "        while 1:\n",
    "            now = []\n",
    "            for n in l_node[-1]:\n",
    "                for son in d_son[n.i]:\n",
    "                    now.append(Node(son, n))\n",
    "\n",
    "            if not now:\n",
    "                break\n",
    "            l_node.append(now)\n",
    "\n",
    "        #从l_node最底层开始处理\n",
    "        ret = [0]*len(parents)\n",
    "\n",
    "        for i in range(len(l_node) - 1, 0, -1):\n",
    "            for n in l_node[i]:\n",
    "                ret[n.i] = n.ret\n",
    "                n.p.add(n)\n",
    "\n",
    "        ret[0] = l_node[0][0].ret\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        child = [[] for _ in range(n)]\n",
    "        inorder = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            p = parents[i]\n",
    "            if p != -1:\n",
    "                child[p].append(i)\n",
    "                inorder[p] += 1\n",
    "\n",
    "        rs = [[] for _ in range(n)]\n",
    "        from collections import deque\n",
    "        dq = deque()\n",
    "        for i in range(n):\n",
    "            if inorder[i] == 0:\n",
    "                rs[i] = [(nums[i], nums[i] + 1)]\n",
    "                dq.append(i)\n",
    "\n",
    "        def merge(x):\n",
    "            hp = []\n",
    "            for c in child[x]:\n",
    "                hp.extend(rs[c])\n",
    "            hp.append((nums[x], nums[x] + 1))\n",
    "            import heapq\n",
    "            heapq.heapify(hp)\n",
    "\n",
    "            ans = []\n",
    "            a, b = heapq.heappop(hp)\n",
    "            while hp:\n",
    "                c, d = heapq.heappop(hp)\n",
    "                if b == c:\n",
    "                    b = d\n",
    "                else:\n",
    "                    ans.append((a, b))\n",
    "                    a, b = c, d\n",
    "            ans.append((a, b))\n",
    "            return ans\n",
    "\n",
    "        # top-sort.\n",
    "        while dq:\n",
    "            x = dq.popleft()\n",
    "            if child[x]:\n",
    "                rs[x] = merge(x)\n",
    "\n",
    "            p = parents[x]\n",
    "            if p != -1:\n",
    "                inorder[p] -= 1\n",
    "                if inorder[p] == 0:\n",
    "                    dq.append(p)\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            a, b = rs[i][0]\n",
    "            # print(i, a, b)\n",
    "            if a == 1:\n",
    "                ans.append(b)\n",
    "            else:\n",
    "                ans.append(1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        #每个节点的子节点\n",
    "        d_son = defaultdict(set)\n",
    "\n",
    "        for i, p in enumerate(parents):\n",
    "            d_son[p].add(i)\n",
    "\n",
    "        class Node:\n",
    "            def __init__(self, i, p=None):\n",
    "                self.i = i\n",
    "                self.p = p\n",
    "\n",
    "                if nums[i] == 1:\n",
    "                    self.nums = {1, 100002}\n",
    "                    self.ret = 2\n",
    "                else:\n",
    "                    self.nums = {nums[i]}\n",
    "                    self.ret = 1\n",
    "\n",
    "            def add(self, n):\n",
    "                if len(self.nums) >= len(n.nums):\n",
    "                    self.nums.update(n.nums)\n",
    "                else:\n",
    "                    n.nums.update(self.nums)\n",
    "                    self.nums = n.nums\n",
    "\n",
    "                if n.ret > self.ret:\n",
    "                    self.ret = n.ret\n",
    "                while self.ret in self.nums:\n",
    "                    self.ret += 1\n",
    "\n",
    "        #将树转为根节点开始的list\n",
    "        l_node = [[Node(0)]]\n",
    "\n",
    "        while 1:\n",
    "            now = []\n",
    "            for n in l_node[-1]:\n",
    "                for son in d_son[n.i]:\n",
    "                    now.append(Node(son, n))\n",
    "\n",
    "            if not now:\n",
    "                break\n",
    "            l_node.append(now)\n",
    "\n",
    "        #从l_node最底层开始处理\n",
    "        ret = [0]*len(parents)\n",
    "\n",
    "        for i in range(len(l_node) - 1, 0, -1):\n",
    "            for n in l_node[i]:\n",
    "                ret[n.i] = n.ret\n",
    "                n.p.add(n)\n",
    "\n",
    "        ret[0] = l_node[0][0].ret\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXN = int(1e9)\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        self.edge = [[] for _ in range(n)]\n",
    "        self.min = [nums[i] for i in range(n)]\n",
    "        self.nums = nums\n",
    "        vis = [0] * (int(1e5)+10)\n",
    "        for i in range(1, n):\n",
    "            if parents[i] != -1:\n",
    "                self.edge[parents[i]].append(i)\n",
    "        for num in nums:\n",
    "            vis[num] = 1\n",
    "        self.ans_list = [0] * n\n",
    "        for i in range(1, 100002):\n",
    "            if not vis[i]:\n",
    "                self.ans_list[0] = i\n",
    "                break\n",
    "        self.dfs1(0)\n",
    "        self.dfs2(0)\n",
    "        return self.ans_list\n",
    "\n",
    "    def dfs1(self, cur):\n",
    "        for nex in self.edge[cur]:\n",
    "            self.dfs1(nex)\n",
    "            self.min[cur] = min(self.min[cur], self.min[nex])\n",
    "\n",
    "    def dfs2(self, cur):\n",
    "        if len(self.edge[cur]) == 0:\n",
    "            return\n",
    "        min1, min2 = min(self.ans_list[cur], self.nums[cur]), max(self.ans_list[cur], self.nums[cur])\n",
    "        for nex in self.edge[cur]:\n",
    "            if self.min[nex] < min1:\n",
    "                min1, min2 = self.min[nex], min1\n",
    "            elif self.min[nex] < min2:\n",
    "                min2 = self.min[nex]\n",
    "        for nex in self.edge[cur]:\n",
    "            if self.min[nex] == min1:\n",
    "                self.ans_list[nex] = min2\n",
    "            else:\n",
    "                self.ans_list[nex] = min1\n",
    "            self.dfs2(nex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, a: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(a)\n",
    "        ans = [0] * n\n",
    "        sons = [[] for _ in range(n)]\n",
    "        vals = [[] for _ in range(n)]\n",
    "        for i, x in enumerate(a):\n",
    "            if x >= 0:\n",
    "                sons[x].append(i)\n",
    "        degrees = [len(ls) for i, ls in enumerate(sons)]\n",
    "        q = [i for i, x in enumerate(degrees) if x == 0]\n",
    "        ans = [0] * n\n",
    "        \n",
    "        def merge(*lists):\n",
    "            # print(lists)\n",
    "            val = []\n",
    "            pq = [(ls[0][0], 0, i) for i, ls in enumerate(lists)]\n",
    "            heapq.heapify(pq)\n",
    "            while pq:\n",
    "                _, idx, i = heapq.heappop(pq)\n",
    "                if val and val[-1][1] == lists[i][idx][0]:\n",
    "                    val[-1][1] = lists[i][idx][1]\n",
    "                else:\n",
    "                    # print(lists[i][idx], lists[i], i, idx)\n",
    "                    val.append(list(lists[i][idx]))\n",
    "                if idx + 1 < len(lists[i]):\n",
    "                    heapq.heappush(pq, (lists[i][idx + 1][0], idx + 1, i))\n",
    "            return val\n",
    "            \n",
    "        while q:\n",
    "            node = q.pop()\n",
    "            if node > 0:\n",
    "                degrees[a[node]] -= 1\n",
    "                if degrees[a[node]] == 0:\n",
    "                    q.append(a[node])\n",
    "            vals[node] = merge(*(vals[x] for x in sons[node]), [[nums[node], nums[node] + 1]])\n",
    "            if vals[node][0][0] > 1:\n",
    "                ans[node] = 1\n",
    "            else:\n",
    "                ans[node] = vals[node][0][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        visit = [False] * (n+2)\n",
    "        visit[0] = True\n",
    "        graph = [list() for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            graph[parents[i]].append(i)\n",
    "        \n",
    "        idx = - 1\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                idx = i\n",
    "                break\n",
    "        if idx == - 1:\n",
    "            return [1]*n\n",
    "        \n",
    "        father = [idx]\n",
    "        while parents[father[-1]] != -1:\n",
    "            father.append(parents[father[-1]])\n",
    "        ans = [1] * n \n",
    "        \n",
    "        def dfsfill(idx, f):\n",
    "            visit[nums[idx]] = True\n",
    "            for c in graph[idx]:\n",
    "                if c != f:\n",
    "                    dfsfill(c, idx)\n",
    "        \n",
    "        def dfs(now, nowidx, f):\n",
    "            if nowidx == -1:\n",
    "                return\n",
    "            dfsfill(nowidx, f)\n",
    "            while now <= n + 1:\n",
    "                if visit[now]:\n",
    "                    now += 1\n",
    "                else:\n",
    "                    ans[nowidx] = now\n",
    "                    dfs(now, parents[nowidx], nowidx)\n",
    "                    return\n",
    "        \n",
    "        dfs(1, father[0], -1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs2(self, rt):\n",
    "        # self.num[rt]\n",
    "        if rt < 0:\n",
    "            return\n",
    "        if self.vis[self.nums[rt]] == 1:\n",
    "            return\n",
    "        self.vis[self.nums[rt]] = 1\n",
    "        for children in self.child[rt]:\n",
    "            self.dfs2(children)\n",
    "\n",
    "    def dfs1(self, rt, dis):\n",
    "        if rt < 0:\n",
    "            return\n",
    "        # self.vis[self.num[rt]] = 1\n",
    "        self.dfs2(rt)\n",
    "        self.vis[self.nums[rt]] = 1\n",
    "        while self.vis[dis + 1] == 1:\n",
    "            dis += 1\n",
    "        # dis += 1\n",
    "        self.ans[rt] = dis + 1\n",
    "        self.dfs1(self.parent[rt], dis)\n",
    "        \n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        self.ans = [1] * len(nums)\n",
    "        self.vis = [0] * (len(nums) + 2)\n",
    "        self.child = [[] for _ in range(len(nums))]\n",
    "        self.parent = parents\n",
    "        self.nums = nums\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            self.child[parents[i]].append(i)\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                self.dfs1(i, 0)\n",
    "                break\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents, nums):\n",
    "        self.tree = [[] for i in range(len(parents))] \n",
    "        self.output = [0 for i in range(len(parents))]\n",
    "        startIndex = 0\n",
    "        for i in range(len(parents)):\n",
    "            if parents[i] != -1:\n",
    "                self.tree[parents[i]].append(i)\n",
    "            else:\n",
    "                startIndex = i\n",
    "        self.nums = nums\n",
    "        self.getGenList(startIndex)\n",
    "        return self.output\n",
    "\n",
    "    def getMinGen(self, genList):\n",
    "        length = len(genList)\n",
    "        mid = int(length / 2)\n",
    "        r = length\n",
    "        l = 0\n",
    "        if r == genList[r - 1]:\n",
    "            return r + 1\n",
    "        while(r > l):\n",
    "            if mid == genList[mid] - 1:\n",
    "                if l == mid:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    l = mid\n",
    "            else:\n",
    "                if r == mid:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            mid = int((l + r) / 2)\n",
    "        return mid + 1\n",
    "\n",
    "\n",
    "    def getGenList(self, idx):\n",
    "        k = None\n",
    "        for e in self.tree[idx]:\n",
    "            if k is None:\n",
    "                k = self.getGenList(e)\n",
    "            else:\n",
    "                tmp = self.getGenList(e)\n",
    "                for i in tmp:\n",
    "                    k.add(i)\n",
    "        if k is None:\n",
    "            k = SortedList()\n",
    "        k.add(self.nums[idx])\n",
    "        self.output[idx] = self.getMinGen(k)\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Set\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        树的问题，应该是子树往上递归包含的值\n",
    "        存储结构用一个数组太长了，用set就好\n",
    "        这题还有难点是需要自己建树\n",
    "        \n",
    "        - 有一点像 124. 二叉树中的最大路径和，都是父节点的值和子节点有关，需要递归获得子节点的返回值\n",
    "        - 注意区别回溯等遍历路径的类型，是父节点传递信息到子节点，这一题不需要，只需要子节点返回信息给父节点即可\n",
    "\n",
    "        优化: \n",
    "        - 父节点的ret肯定>=子节点的ret\n",
    "        - 不存在基因值1，直接返回1\n",
    "        \"\"\"\n",
    "        n = len(parents)\n",
    "        tree = [[] for _ in range(n)]   # 每个元素表示当前节点的子节点，可以满足我们从上往下遍历树的需求\n",
    "        ret = [1 for _ in range(n)]\n",
    "\n",
    "        if 1 not in nums:  # 不存在基因值为 1 的点\n",
    "            return ret\n",
    "\n",
    "        for i, p in enumerate(parents):\n",
    "            if p == -1:\n",
    "                continue\n",
    "            tree[p].append(i)\n",
    "        \n",
    "        \n",
    "        def dfs(nums, tree, node, ret):\n",
    "            path:Set = None\n",
    "            retStart = 1\n",
    "            for nei in tree[node]:\n",
    "                path_new, reti = dfs(nums, tree, nei, ret)\n",
    "                retStart = max(retStart, reti)\n",
    "                if not path:\n",
    "                    path = path_new\n",
    "                else:\n",
    "                    for s in path_new:\n",
    "                        path.add(s)\n",
    "            if not path:\n",
    "                path = set()\n",
    "            path.add(nums[node])\n",
    "            reti = find(path,retStart)\n",
    "            ret[node] = reti\n",
    "            # print(node, path, reti, retStart)\n",
    "            return path, reti\n",
    "\n",
    "        def find(path, start)->int:\n",
    "            # 找到最小的0，也就是缺少的基因\n",
    "            while start in path:\n",
    "                start += 1\n",
    "            return start\n",
    "\n",
    "        dfs(nums, tree, 0, ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find_1st_missing_postivie(self, nums: List[int]) -> int:\n",
    "        nlen = len(nums)\n",
    "        flagged = [1 for _ in range(nlen)]\n",
    "\n",
    "        for i in nums:\n",
    "            if 0 < i <= nlen:\n",
    "                flagged[i - 1] = 0\n",
    "\n",
    "        for i in range(nlen):\n",
    "            if flagged[i] == 1:\n",
    "                return i + 1\n",
    "\n",
    "        return nlen + 1\n",
    "\n",
    "    def smallestMissingValueSubtree(\n",
    "        self, parents: List[int], nums: List[int]\n",
    "    ) -> List[int]:\n",
    "        nlen = len(parents)\n",
    "        childs = [[] for _ in range(nlen)]\n",
    "        sub_gens_min = [10**5 + 1 for _ in range(nlen)]\n",
    "        ans = [0 for _ in range(nlen)]\n",
    "\n",
    "        # Nodes whose subtree has 1 included, this means its mlg is not 1\n",
    "        # In DFS traversal, bottom node is in left of the list.\n",
    "        nodes_of_interest = []\n",
    "\n",
    "        # Construct list for direct child node list.\n",
    "        # Loop stargt from 1 not 0 as parents[0] is always -1\n",
    "        # Reminded that the tree is not limited to binary tree.\n",
    "        for i in range(1, nlen):\n",
    "            childs[parents[i]].append(i)\n",
    "\n",
    "        # DFS to\n",
    "        # - construct the tree from bottom up\n",
    "        # - determine whether a subtree has 1 included\n",
    "        # - record the min gen value for each sub tree.\n",
    "        def dfs(n):\n",
    "            nonlocal childs, ans\n",
    "\n",
    "            flag_having_one = False\n",
    "            if nums[n] == 1:\n",
    "                flag_having_one = True\n",
    "\n",
    "            # sub_gens[n].append(nums[n])\n",
    "            if childs[n]:\n",
    "                for i in childs[n]:\n",
    "                    # calling to dfs(i) should be in 1st place in order to avoid the optimization from compiler or intepretter.\n",
    "                    flag_having_one = dfs(i) or flag_having_one\n",
    "\n",
    "                    sub_gens_min[n] = min(sub_gens_min[n], sub_gens_min[i])\n",
    "\n",
    "            sub_gens_min[n] = min(nums[n], sub_gens_min[n])\n",
    "\n",
    "            if not flag_having_one:\n",
    "                ans[n] = 1\n",
    "            else:\n",
    "                nodes_of_interest.append(n)\n",
    "\n",
    "            return flag_having_one\n",
    "\n",
    "        dfs(0)\n",
    "\n",
    "\n",
    "        # Traverse the tree from the root to get mlg(missing least gen)\n",
    "        if ans[0] == 1:\n",
    "            return [1 for _ in range(nlen)]\n",
    "        else:\n",
    "            ans[0] = self.find_1st_missing_postivie(nums.copy())\n",
    "\n",
    "            # Only update nodes whose subtree doesnt have 1 included.\n",
    "            for i in range(len(nodes_of_interest) - 2, -1, -1):\n",
    "                # Check firstly this node's parent whether has other sub node.\n",
    "                min_gen = min(10**5 + 1, nums[parents[nodes_of_interest[i]]])\n",
    "                # The looping below supports not only binary tree. Tree with more sub nodes is also OK.\n",
    "                for c in childs[parents[nodes_of_interest[i]]]:\n",
    "                    if c == nodes_of_interest[i]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        min_gen = min(min_gen, sub_gens_min[c])\n",
    "                        \n",
    "                if ans[parents[nodes_of_interest[i]]] > min_gen:\n",
    "                    ans[nodes_of_interest[i]] = min_gen\n",
    "                else:\n",
    "                    ans[nodes_of_interest[i]] = ans[parents[nodes_of_interest[i]]]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        edge = [[] for _ in range(n)]\n",
    "        for i, x in enumerate(parents):\n",
    "            if x == -1:\n",
    "                root = i\n",
    "            else:\n",
    "                edge[x].append(i)\n",
    "        \n",
    "        # dsu on tree\n",
    "        heavy = [-1] * n\n",
    "        def dfs1(r):\n",
    "            pmax = -1\n",
    "            maxW = 0\n",
    "            s = 0\n",
    "            for i in edge[r]:\n",
    "                c = dfs1(i)\n",
    "                if c > maxW:\n",
    "                    maxW = c\n",
    "                    pmax = i \n",
    "                s += c\n",
    "            heavy[r] = pmax\n",
    "            return s + 1\n",
    "        dfs1(root)\n",
    "\n",
    "        ans = [1] * n\n",
    "        def dfs2(r):\n",
    "            if r == -1:\n",
    "                return set()\n",
    "            geneSet = dfs2(heavy[r])\n",
    "            ca = ans[heavy[r]] if heavy[r] >= 0 else 1\n",
    "            for i in edge[r]:\n",
    "                if i == heavy[r]:\n",
    "                    continue\n",
    "                geneSet.update(dfs2(i))\n",
    "                ca = max(ca, ans[i]) \n",
    "\n",
    "            geneSet.add(nums[r])\n",
    "            while ca in geneSet:\n",
    "                ca += 1\n",
    "            ans[r] = ca\n",
    "            return geneSet\n",
    "        dfs2(root)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        tree = [[] for _ in range(len(nums))]\n",
    "        res = [1 for _ in range(len(nums))]\n",
    "        for i in range(1, len(nums)):\n",
    "            tree[parents[i]].append(i)\n",
    "\n",
    "        visited = [False]*len(nums)\n",
    "        node_set = set()\n",
    "\n",
    "        def dfs(x):\n",
    "            visited[x] = True\n",
    "            node_set.add(nums[x])\n",
    "            for e in tree[x]:\n",
    "                if not visited[e]:\n",
    "                    dfs(e)\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                node = i\n",
    "                break\n",
    "        else:\n",
    "            node = 1 \n",
    "        p = 1\n",
    "        while node != -1:\n",
    "            dfs(node)\n",
    "            while p in node_set:\n",
    "                p += 1\n",
    "            res[node] = p\n",
    "            node = parents[node]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            g[parents[i]].append(i)\n",
    "\n",
    "        ans = [1]*n \n",
    "        def dfs1(i):\n",
    "            if nums[i] == 1: ans[i] = 0\n",
    "            for j in g[i]:\n",
    "                dfs1(j)\n",
    "                if ans[j] == 0: ans[i] = 0\n",
    "\n",
    "        mark = [0]*(10**5+1)\n",
    "        def dfs(i):\n",
    "            adjs = [j for j in g[i] if ans[j]==0] + [j for j in g[i] if ans[j]==1]\n",
    "            for j in adjs:\n",
    "                dfs(j)\n",
    "            mark[nums[i]] = 1\n",
    "            if ans[i] == 0:\n",
    "                idx = ans[adjs[0]] if adjs else 1\n",
    "                while idx <= 10**5:\n",
    "                    if mark[idx] == 0: \n",
    "                        ans[i] = idx\n",
    "                        break\n",
    "                    idx += 1        \n",
    "                if idx > 10**5: ans[i] = idx\n",
    "            \n",
    "        dfs1(0)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "\n",
    "        #建子树\n",
    "        self.children = defaultdict(list)\n",
    "        for child, parent in enumerate(parents):\n",
    "            self.children[parent].append(child)\n",
    "        #1的位置\n",
    "        self.one = 0\n",
    "        ans = [1 for _ in range(len(parents))]\n",
    "        #最小基因值\n",
    "        mex = 1\n",
    "\n",
    "        def find1(node):\n",
    "            if nums[node] == 1:\n",
    "                self.one = node\n",
    "                return True\n",
    "            else:\n",
    "                for child in self.children[node]:\n",
    "                    if find1(child):\n",
    "                        return True\n",
    "                return False\n",
    "        # 没有1基因，返回全1\n",
    "        if not find1(0):\n",
    "            return ans\n",
    "\n",
    "        # DFS 找到当前子树（含当前节点）的基因集合并记录\n",
    "        self.gene = [False] * 100010\n",
    "\n",
    "        def findGene(node):\n",
    "            self.gene[nums[node]] = True\n",
    "            if not self.children[node]:\n",
    "                return\n",
    "            else:\n",
    "                for child in self.children[node]:\n",
    "                    if self.gene[nums[child]] == False:\n",
    "                        findGene(child)\n",
    "                return\n",
    "\n",
    "        node = self.one\n",
    "        while node != -1:\n",
    "            findGene(node)\n",
    "            while mex < 100010:\n",
    "                if self.gene[mex] == False:\n",
    "                    break\n",
    "                mex += 1\n",
    "            ans[node] = mex\n",
    "            node = parents[node]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            g[parents[i]].append(i)\n",
    "\n",
    "        ans = [1]*n \n",
    "        def dfs1(i):\n",
    "            if nums[i] == 1: ans[i] = 0\n",
    "            for j in g[i]:\n",
    "                dfs1(j)\n",
    "                if ans[j] == 0: ans[i] = 0\n",
    "\n",
    "        s = set()\n",
    "        def dfs(i):\n",
    "            adjs = [j for j in g[i] if ans[j]==0] + [j for j in g[i] if ans[j]==1]\n",
    "            for j in adjs:\n",
    "                dfs(j)\n",
    "            s.add(nums[i])\n",
    "            if ans[i] == 0:\n",
    "                miss = ans[adjs[0]] if adjs else 1\n",
    "                while miss in s:\n",
    "                    miss += 1      \n",
    "                ans[i] = miss\n",
    "            \n",
    "        dfs1(0)\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        # 深度优先遍历\n",
    "        # 根据题意一共不大于100010的数的大小以及节点的数目\n",
    "        # 初始化 需要遍历计算缺少的那个数字 now\n",
    "        # 首先找出来有1 的分支，对于没有1的子树，缺少的数字就是1 \n",
    "        has1 = [False] * 100010\n",
    "        vis = [False] * 100010 # 寻找缺少数字 利用的数组\n",
    "        # 找出1 需要记忆的一种遍历方式\n",
    "        # 首先构建 树\n",
    "        tree_node = defaultdict(list)\n",
    "        ans = [1] * 100010\n",
    "        for i in range(len(parents)):\n",
    "            tree_node[parents[i]].append(i)\n",
    "        # 找出1\n",
    "        def dfs_find1(node):\n",
    "            if nums[node] == 1: \n",
    "                has1[node] = True\n",
    "            else:\n",
    "                has1[node] = False\n",
    "            for v in tree_node[node]:\n",
    "                dfs_find1(v)\n",
    "                has1[node] |= has1[v] # 如果子树是有1的需要更新父节点的状态\n",
    "            if not has1[node]:\n",
    "                ans[node] = 1 # 对于确实是没有1的子树，对应的位置的答案更新为1\n",
    "        \n",
    "        # 开始计算值\n",
    "        def dfs(node):\n",
    "            for v in tree_node[node]:\n",
    "                dfs(v)\n",
    "            vis[nums[node]] = True\n",
    "\n",
    "        # 计算不是1的节点的ans值 \n",
    "        global n\n",
    "\n",
    "        n = 1\n",
    "        def dfs_findn1(node):\n",
    "            global n\n",
    "            if not has1[node]: \n",
    "                return\n",
    "            for v in tree_node[node]:\n",
    "                if has1[v]:\n",
    "                    dfs_findn1(v)\n",
    "\n",
    "            for v in tree_node[node]:\n",
    "                if not has1[v]:\n",
    "                    dfs(v)\n",
    "\n",
    "            vis[nums[node]] = True\n",
    "            while vis[n]:\n",
    "                n += 1\n",
    "            ans[node] = n\n",
    "        \n",
    "        dfs_find1(0)\n",
    "        dfs_findn1(0)\n",
    "        return ans[:len(nums)]\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        总体思路：\n",
    "        - 深度优先遍历（递归）每个节点，自顶向上地返回区间\n",
    "        - 将左右子树返回的区间以及自身代表的单个数字区间进行合并\n",
    "        - 合并后找到最小的缺失值\n",
    "        '''\n",
    "        def merge(intervals: List[List[int]]) -> List[List[int]]:\n",
    "            intervals.sort(key=lambda x:x[0])\n",
    "            result=[]\n",
    "            if len(intervals):\n",
    "                result=[intervals[0]]\n",
    "                for i in range(1, len(intervals)):\n",
    "                    if result[-1][1]>=intervals[i][0]-1:\n",
    "                        result[-1][0]=min(result[-1][0], intervals[i][0])\n",
    "                        result[-1][1]=max(result[-1][1], intervals[i][1])\n",
    "                    else:\n",
    "                        result.append(intervals[i])\n",
    "            return result\n",
    "        result=[1]*len(parents)\n",
    "        parent_child_dict=dict()\n",
    "        for i in range(len(parents)):\n",
    "            if parents[i] not in parent_child_dict:\n",
    "                parent_child_dict[parents[i]]=[i]\n",
    "            else:\n",
    "                parent_child_dict[parents[i]].append(i)\n",
    "        \n",
    "        def recur(node):\n",
    "            if node not in parent_child_dict:\n",
    "                # 是叶子节点\n",
    "                if nums[node]>1:\n",
    "                    result[node]=1\n",
    "                else:\n",
    "                    result[node]=2\n",
    "                return [[nums[node], nums[node]]]\n",
    "            else:\n",
    "                # 如果不是叶子节点就深度遍历\n",
    "                current_range_list=[]\n",
    "                for child_node in parent_child_dict[node]:\n",
    "                    temp_range_list=recur(child_node)\n",
    "                    current_range_list+=temp_range_list\n",
    "                \n",
    "                current_range_list.append([nums[node], nums[node]])\n",
    "                current_range_list=merge(current_range_list)\n",
    "                index=0\n",
    "                if current_range_list[0][0]>1:\n",
    "                    result[node]=1\n",
    "                else:\n",
    "                    result[node]=current_range_list[0][1]+1\n",
    "                return current_range_list\n",
    "        recur(0)\n",
    "        return result                    \n",
    "            \n",
    "\n",
    "\n",
    "        # def recur_dfs():\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            g[parents[i]].append(i)\n",
    "\n",
    "        ans = [1]*n \n",
    "        def dfs1(i):\n",
    "            if nums[i] == 1: ans[i] = 0\n",
    "            for j in g[i]:\n",
    "                dfs1(j)\n",
    "                if ans[j] == 0: ans[i] = 0\n",
    "\n",
    "        s = set()\n",
    "        def dfs(i):\n",
    "            idx1 = 0\n",
    "            for k, j in enumerate(g[i]):\n",
    "                if ans[j] == 0: idx1 = k\n",
    "            adjs = g[i][idx1:]+g[i][:idx1]\n",
    "            for j in adjs:\n",
    "                dfs(j)\n",
    "            s.add(nums[i])\n",
    "            if ans[i] == 0:\n",
    "                miss = ans[adjs[0]] if adjs else 1\n",
    "                while miss in s:\n",
    "                    miss += 1      \n",
    "                ans[i] = miss\n",
    "            \n",
    "        dfs1(0)\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        ans = [0] * n\n",
    "        sub = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            sub[parents[i]].append(i)\n",
    "\n",
    "        def merge(arr, l, r):\n",
    "            idx = bisect.bisect_left(arr, [l, r])\n",
    "            b_m = False\n",
    "            if idx > 0 and arr[idx - 1][1] == l - 1:\n",
    "                b_m = True\n",
    "                arr[idx - 1][1] = r\n",
    "            if idx < len(arr) and arr[idx][0] == r + 1:\n",
    "                b_m = True\n",
    "                arr[idx][0] = l\n",
    "            if idx > 0 and idx < len(arr) and arr[idx - 1][1] >= arr[idx][0]:\n",
    "                arr[idx - 1][1] = arr[idx][1]\n",
    "                del arr[idx]\n",
    "            return b_m\n",
    "\n",
    "        def dfs(root):\n",
    "            ret = [[nums[root], nums[root]]]\n",
    "            for child in sub[root]:\n",
    "                s_arr = dfs(child)\n",
    "                for l, r in s_arr:\n",
    "                    b_m = merge(ret, l, r)\n",
    "                    if not b_m:\n",
    "                        bisect.insort(ret, [l, r])\n",
    "            ans[root] = 1 if ret[0][0] != 1 else (ret[0][1] + 1)\n",
    "            return ret\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(999999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        link = {}\n",
    "        for i, p in enumerate(parents):\n",
    "            if p != -1:\n",
    "                if p not in link:\n",
    "                    link[p] = []\n",
    "                link[p].append(i)\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = [1] * n\n",
    "        ones = [0] * (10**5 + 5)\n",
    "\n",
    "        def dfs1(node, dep) -> bool:\n",
    "            if nums[node] == 1:\n",
    "                ones[node] = 1\n",
    "                return True\n",
    "\n",
    "            if node in link:\n",
    "                for ne in link[node]:\n",
    "                    if dfs1(ne, dep+1):\n",
    "                        ones[node] = 1\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        dfs1(0, 1)\n",
    "\n",
    "        def dfs2(node):\n",
    "            if node not in link:\n",
    "                if ones[node]:\n",
    "                    ans[node] = 2\n",
    "                return {nums[node]}\n",
    "\n",
    "            else:\n",
    "                arr = []\n",
    "                start_pos = 1\n",
    "                for ne in link[node]:\n",
    "                    arr.append(dfs2(ne))\n",
    "                    start_pos = max(start_pos, ans[ne])\n",
    "\n",
    "                arr.sort(key = lambda x : len(x), reverse = True)\n",
    "                s = arr[0]\n",
    "                for i in range(1, len(arr)):\n",
    "                    s |= arr[i]\n",
    "                s.add(nums[node])\n",
    "\n",
    "                for i in range(start_pos, 10**5 + 5):\n",
    "                    if i not in s:\n",
    "                        ans[node] = i\n",
    "                        break\n",
    "\n",
    "                return s\n",
    "\n",
    "        dfs2(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        # 给一个stl找缺失值MEX可以二分\n",
    "        # 考虑使用区间计数法\n",
    "        n = len(parents)\n",
    "        g = defaultdict(list)\n",
    "        for i, v in enumerate(parents):\n",
    "            if v != -1:\n",
    "                g[v].append(i)\n",
    "        #print(g)\n",
    "        if 1 not in nums:\n",
    "            return [1] * n\n",
    "\n",
    "        def merge(segs):\n",
    "            segs.sort()\n",
    "            res = []\n",
    "            l, r = segs[0]\n",
    "            m = len(segs)\n",
    "            for i in range(1, m):\n",
    "                tl, tr = segs[i]\n",
    "                if tl == r + 1:\n",
    "                    r = tr\n",
    "                else:\n",
    "                    res.append([l, r])\n",
    "                    l, r = tl, tr\n",
    "            res.append([l, r])\n",
    "            return res\n",
    "\n",
    "\n",
    "        ans = [0] * n\n",
    "        def dfs(cur, pa): # 返回子树包含的区间\n",
    "            #print(cur, pa)\n",
    "            nonlocal ans\n",
    "            segs = [[nums[cur], nums[cur]]]\n",
    "            for nxt in g[cur]:\n",
    "                if nxt != pa:\n",
    "                    segs.extend(dfs(nxt, cur))\n",
    "            segs = merge(segs)\n",
    "            if segs[0][0] != 1:\n",
    "                ans[cur] = 1\n",
    "            else:\n",
    "                ans[cur] = segs[0][1] + 1\n",
    "            return segs\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        n = len(parents)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parents[i]].append(i)\n",
    "\n",
    "        ans = [1] * n\n",
    "        def dfs(x):\n",
    "            visx = {nums[x]}\n",
    "            for y in g[x]:\n",
    "                visy = dfs(y)\n",
    "                if len(visy) > len(visx):\n",
    "                    visx, visy = visy, visx\n",
    "                visx |= visy\n",
    "                if ans[y] > ans[x]:\n",
    "                    ans[x] = ans[y]\n",
    "            \n",
    "            while ans[x] in visx:\n",
    "                ans[x] += 1\n",
    "            return visx\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 找每个结点的最小缺失基因\n",
    "# 这看起来就是从底层慢慢回去\n",
    "# 后跟遍历 先建图吧\n",
    "class Solution:\n",
    "    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:\n",
    "        graph = [[] for _ in range(len(parents))]\n",
    "        for i, j in enumerate(parents):\n",
    "            if j == -1:\n",
    "                continue\n",
    "            else:\n",
    "                graph[j].append(i)\n",
    "        res = [1] * len(parents)\n",
    "\n",
    "        # 如何合并2边的结果呢\n",
    "        # 要返回集合和最小值 做一个合并操作\n",
    "        def post_order(idx):\n",
    "            used = {nums[idx]}\n",
    "            for i in graph[idx]:\n",
    "                t_set, t_val = post_order(i)\n",
    "                res[idx] = max(res[idx], t_val)\n",
    "                if len(t_set) > len(used):\n",
    "                    used, t_set = t_set, used\n",
    "                used.update(t_set)\n",
    "            # 把这个结果返回回去 省时间 而不是返回一个初始max_val\n",
    "            while res[idx] in used:\n",
    "                res[idx] += 1\n",
    "            return used, res[idx]\n",
    "\n",
    "        post_order(0)\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
